﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using snat.model;

namespace snat.algorithms.network.Metrics
{
    public class UndirectedReachability
    {



        public static HashSet<List<OverlayNode>> OverlayConnectedComponents(HashSet<OverlayNode> blocklist = null){
            blocklist = blocklist ?? new HashSet<OverlayNode>();
            List<BaseNode> allNodes = NetworkModel.Instance.Nodes.Values.ToList();
             List<OverlayNode> overlayNodes = allNodes.Where(e => e is OverlayNode).ToList().ConvertAll(e=>e as OverlayNode);
            HashSet<BaseNode> unexplored = new HashSet<BaseNode>(overlayNodes);


            HashSet<List<OverlayNode>> result = new HashSet<List<OverlayNode>>();
            while (unexplored.Count > 0) {
                BaseNode nucleus = unexplored.First();
                unexplored.Remove(nucleus);
                if (blocklist.Contains(nucleus)) continue;
                List<OverlayNode> newlist = new List<OverlayNode>();
                newlist.AddRange(OverlayUndirectedReachableFrom((OverlayNode)nucleus, blocklist));
                unexplored.RemoveWhere(e => newlist.Exists(f => f.ID == e.ID));
                result.Add(newlist);
            }

            return result;
        }


        public static List<OverlayNode> OverlayUndirectedReachableFrom(OverlayNode start, HashSet<OverlayNode> blocklist = null)
        {
            HashSet<OverlayNode> explored = new HashSet<OverlayNode>();
            Queue<OverlayNode> unexplored = new Queue<OverlayNode>();
            unexplored.Enqueue(start);


            while (unexplored.Count > 0) {
                OverlayNode exploring = unexplored.Dequeue();
                if (explored.Contains(exploring) || blocklist.Contains(exploring)) continue; //check if it's been double enqueued - faster than checkign queue
                List<BaseNode> outneighbors = exploring.OverlayOutEdges.ConvertAll(e => NetworkModel.Instance.Nodes[e.Target.ID]);
                List<BaseNode> inneighbors = exploring.OverlayInEdges.ConvertAll(e => NetworkModel.Instance.Nodes[e.Source.ID]);
                IEnumerable<BaseNode> allneighbors = outneighbors.Union(inneighbors).Where(e=>!explored.Contains(e));
                foreach (OverlayNode b in allneighbors) unexplored.Enqueue(b);
                explored.Add(exploring);
            }

            return explored.ToList();
        }
    }
}
